package com.algorithm.base.backtracking;

import java.util.*;

/**
 * 491. 递增子序列
 *
 * @author Amadeus
 * @date 2023/11/10
 */
public class FindSubsequences {

    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> deque = new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<Integer> set = new HashSet<>();
        backTracking(0, nums, set);
        return result;
    }

    public void backTracking(int index, int[] nums, Set<Integer> set) {
        for (int i = index; i < nums.length; i++) {
            if ((!deque.isEmpty() && nums[i] < deque.getLast())
                    || set.contains(nums[i])) {
                continue;
            }
            deque.addLast(nums[i]);
            set.add(nums[i]);
            if (deque.size() > 1) {
                result.add(new ArrayList<>(deque));
            }
            backTracking(i + 1, nums, set);
            deque.removeLast();
            set.remove(nums[i]);
        }
    }

}
